#include<stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define M 8
#define N 8
#define MaxSize 100

typedef struct
{  int i;			//��ǰ������к�   
   int j;			//��ǰ������к�
} Box;

typedef struct
{  Box data[MaxSize];
   int length;			//·������
}  PathType;			//����·������

int mg[M+2][N+2]=
{
    {1,1,1,1,1,1,1,1,1,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,0,0,1,1,0,0,1},
    {1,0,1,1,1,0,0,0,0,1},
    {1,0,0,0,1,0,0,0,0,1},
    {1,0,1,0,0,0,1,0,0,1},
    {1,0,1,1,1,0,1,1,0,1},
    {1,1,0,0,0,0,0,0,0,1},
    {1,1,1,1,1,1,1,1,1,1}
};
//int mg[M+2][N+2]=  	//M=4,N=4
//{  {1,1,1, 1,1,1},
//   {1,0, 0, 0, 1, 1},
//   {1, 0, 1, 0, 0, 1},
//   {1, 0, 0, 0, 1, 1},
//   {1, 1, 0, 0, 0, 1},
//   {1, 1, 1, 1, 1, 1}  };

int count=0;

PathType a;
void InitPathType(PathType *s)
{  s=(PathType *)malloc(sizeof(PathType));
   s->length=0;
} 
void mgpath(int xi,int yi,int xe,int ye,PathType path)
//���·��Ϊ:(xi,yi)  ?  (xe,ye)
{  int di,k,i,j,len;
  // Box e;
   
    //printf("helloworld!\n");
   if  (xi==xe && yi==ye)
   {  
		path.data[path.length].i = xi;
		path.data[path.length].j = yi;
      path.length++;
      printf("  path %d ",count);
      count++;
      for (k=0;k<path.length;k++)
      {  printf("\t(%d,%d)",path.data[k].i, path.data[k].j);
         if ((k+1)%5==0)	//ÿ���ÿ5�������һ��
           printf("\n");
      }
      printf("\n");
   }
	else//(xi,yi)���ǳ���
	{
		if (mg[xi][yi]==0)	//(xi,yi)��һ�����߷���
		{
			di=0;
	   		while (di<4)      	//����(xi,yi)���ܵ�ÿһ�����ڷ�λdi
			{ 
				switch(di)      	//�ҷ�λdi��Ӧ�ķ���(i,j)
				{
				   case 0:i=xi-1; j=yi;   break;
				   case 1:i=xi;   j=yi+1; break;
				   case 2:i=xi+1; j=yi;   break;
				   case 3:i=xi;   j=yi-1; break;
				}
            // e.i=xi;
            // e.j=yi;
            // //len=path.length;
            // path.data[path.length]=e;
            //printf("helloworld!\n");
				path.data[path.length].i = xi;
				path.data[path.length].j = yi;
				path.length++;    	//·��������1                             
				mg[xi][yi]=-1;      	//���������ظ���·��
             
				mgpath(i,j,xe,ye,path);
				
				
				path.length--;	//����һ������
				  mg[xi][yi]=0;		//�ָ�(xi,yi)Ϊ����                
				  di++;
				}   			//-while 
        }     				//- if (mg[xi][yi]==0)
    }    				//-�ݹ���

}

int main()
{
	//InitPathType(&a);
	mgpath(1,1,M,N,a);
    //printf("���Թ�����û�н�!");
	//while(1);
   system("pause");
   return 0;
	
} 

	
